package com.tgy.algorithm.base._递归;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class _01_获取字符串所有子序列 {


    /**
     *           abc
     *           a ab abc
     *           b bc
     *           c
     *
     *
     * 获取字符串的所有字串
     * @param content
     * @return
     */
    public static List<String> getAllSubStr(String content) {

        char[] charArray = content.toCharArray();
        int len = charArray.length;
        /**
         *
         *  abc
         *  bc
         *  a
         *
         */
        HashSet<String> strs = new HashSet<>();

        for (int i = 0; i < len; i++) {
            StringBuilder sb = new StringBuilder();
            sb.append(charArray[i]);
            if (!strs.contains(sb.toString())) {
                strs.add(new String(sb));
            }
            for (int j = i+1; j < len; j++) {
                sb.append(charArray[j]);
                if (!strs.contains(sb.toString())) {
                    strs.add(new String(sb));
                }
            }
        }

        System.out.println(strs);

        return null;
    }

    /**
     * 获取字符串所有子序列
     *  abc
     *  abc ab a
     *  b
     *
     *
     *
     *
     * @param content
     * @return
     */
    public static HashSet<String> getAllSubSeq(String content) {
        char[] charArray = content.toCharArray();
        HashSet<String> strings = new HashSet<>();
        doGetAllSubSeq(charArray,"",0,strings);
        return strings;
    }

    public static void doGetAllSubSeq(char[] chArr,String pre,int level,HashSet<String> res) {

        if (chArr.length == level) {
            if (!pre.isEmpty()) {
                res.add(pre);
            }
            return;
        }

        // 不要
        doGetAllSubSeq(chArr,pre,level+1,res);
        // 要
        doGetAllSubSeq(chArr,pre+chArr[level],level+1,res);
    }


    /**
     *    abc
     *    aaa
     *    aab
     *    aac
     *    aba
     *    abb
     *    abc
     *    baa
     *    bab
     *    bac
     *    bba
     *    bbb
     *    bbc
     *    bca
     *    bcb
     *    bcc
     *
     * @param content
     * @return
     */
    public static HashSet<String> getAllRank(String content) {

        HashSet<String> res = new HashSet<>();
        doGetAllRank(content.toCharArray(),"",0,res);
        return res;
    }

    public static void doGetAllRank(char[] cha,String pre,int level,HashSet<String> res) {
        if (cha.length == level) {
            res.add(pre);
            return;
        }

        for (char ch:cha){
            doGetAllRank(cha,pre+ch,level+1,res);
        }
    }

    public static List<List<Integer>> getNumAllRank(int[] arr) {

        ArrayList<List<Integer>> lists = new ArrayList<>();
        doGetNumAllRank(arr,new ArrayList<Integer>(),lists);
        return lists;
    }

    public static void doGetNumAllRank(int[] arr,List<Integer> res,ArrayList<List<Integer>> lists) {
        if (arr.length == res.size()) {
            lists.add(new ArrayList<>(res));
            return;
        }

        for (Integer i : arr) {
            res.add(i);
            doGetNumAllRank(arr,res,lists);
//            res.remove(i);
            // 这里必须使用 index进行删除，不然会出现删除之前的res相同的int值
            res.remove(res.size() - 1);
        }
    }

    public static List<List<Integer>> getNumAllRank01(int[] nums) {

        ArrayList<List<Integer>> lists = new ArrayList<>();
        doGetNumAllRank01(nums,0,lists);
        return lists;
    }

    public static void doGetNumAllRank01(int[] nums,int level,List<List<Integer>> ret) {

        if (nums.length == level) {
            ArrayList<Integer> integers = new ArrayList<>();
            for (int num : nums) {
                integers.add(num);
            }
            ret.add(integers);
            return;
        }

        for (int i = 0;i < nums.length;i++) {
            swap(nums,level,i);
            doGetNumAllRank01(nums,level+1,ret);
            swap(nums,level,i);
        }

    }

    public static void swap(int[] nums,int i,int j) {
        if (i == j) {
            return;
        }
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
//        getAllSubStr("abc");
//        HashSet<String> subSeq = getAllSubSeq("abc");
//        System.out.println(subSeq);
//        HashSet<String> allRank = getAllRank("abc");
//        System.out.println(allRank);
//        System.out.println(allRank.size());
//        ArrayList<List<Integer>> numAllRank = getNumAllRank(new int[]{1, 2, 3});
//        System.out.println(numAllRank);
//        System.out.println(numAllRank.size());
//        List<List<Integer>> allRank = getNumAllRank(new int[]{1, 2, 3});
//
//        allRank.forEach(System.out::println);
//        System.out.println(allRank.size());
        List<List<Integer>> numAllRank01 = getNumAllRank01(new int[]{1, 2, 3});
        System.out.println(numAllRank01.size());
        numAllRank01.forEach(System.out::println);
    }
}
